/*
   排序算法正常，目前无错误
*/
#include <iostream>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <cstdio>
#include <malloc.h>

using namespace std;

#define MAXSIZE 10

typedef struct List
{
	int data;
	struct List * pNext;
}List, *pList;

pList Create_list()
{
	pList L = (pList)malloc(sizeof(pList));
	if (NULL == L)
	{
		printf("创建失败！\n");
		exit(-1);
	}
	else
	{
		L->pNext = NULL;
		//printf("创建成功!\n");
		return L;
	}
}

void Add_back(pList L, int val)
{
	//申请一个新的节点存放数据
	//这不是真正的节点，这是一个指向新节点的指针变量
	//所有的malloc都可以这么理解
	//我们并不需要关心真正的结点在哪里，我们只需要知道能有一个指针指向这个节点，能够供我们访问就好了

	pList pNew = (pList)malloc(sizeof(List));
	//赋值；指针域指向NULL，表明尾部节点
	if (pNew == NULL)
	{
		exit(-1);
	}
	pNew->data = val;
	pNew->pNext = NULL;

	//定义一个结构体指针指向头节点
	pList pIter = L;

	//使指针指向链表的最后一个结点 
	while (pIter->pNext != NULL)
	{
		pIter = pIter->pNext;
	}

	//最后一个结点指向新节点，完成添加
	pIter->pNext = pNew;
}

//获取元素个数（链表的长度还要再加上1（头节点已经存在））
int Length_list(pList L)
{
	int length = 0;
	pList pIter = L->pNext;
	while (pIter != NULL)
	{
		length++;
		pIter = pIter->pNext;
	}
	return length;
}

//遍历链表
void Traverse_list(pList L)
{
	printf("\n");
	//先判断链表是否为空
	if (L->pNext == NULL)
	{
		printf("链表为空！\n");
	}
	else
	{
		//依次遍历输出元素
		while (L->pNext != NULL)
		{
			printf("%d ", L->pNext->data);
			L = L->pNext;
		}
		printf("\n");
	}
}

//链表的冒泡排序算法
void sort_list(pList L)
{
	int temp;
	for(pList p = L->pNext; p->pNext != NULL; p = p->pNext)
	{
		for(pList q = p->pNext; q != NULL; q = q->pNext)
		{
			if(p->data > q->data)
			{
				temp = p->data;
				p->data = q->data;
				q->data = temp;
			}
		}
	}

}

int main(void)
{
	//播种
	srand(time(NULL));

	//创建链表
    pList L;
    L = Create_list();

	//随机赋值
	for(int i = 0; i < MAXSIZE; i++)
	{
		Add_back(L,rand()%101);
	}

	//遍历输出->排序->遍历输出
	Traverse_list(L);
	sort_list(L);
	Traverse_list(L);

    return 0;
}

